// 200
package AVL树;

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree<E> {

    protected int size;
    protected Node<E> root;


    // 返回二叉树的高度, 递归形式
    public int height() {
        return this.height(this.root);
    }

    protected int height(Node<E> node) {
        if (node == null) return 0;
        return 1 + Math.max(this.height(node.left), height(node.right));
    }

    // 返回二叉树的高度, 层序遍历
    public int height2() {
        if (this.root == null) {
            return 0;
        }
        int height = 0;
        int levelSize = 1;

        Queue<Node<E>> queue = new LinkedList<Node<E>>();
        queue.offer(this.root);

        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            levelSize--;
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            if (levelSize == 0) { // 监听状态， 判断这层有没有遍历完，然后更新状态
                height++;
                levelSize = queue.size();
            }
        }

        return height;
    }

    // 后序遍历
    public void postorderTraversal() {
        this.postorderTraversal(root);
    }

    // 后序遍历， 先子节点后父节点的遍历方式
    protected void postorderTraversal(Node<E> node) {
        if (node == null) {
            return;
        }
        this.inorderTraversal(node.left);
        this.inorderTraversal(node.right);
        System.out.println(node.element);
    }

    // 中序遍历
    public void inorderTraversal() {
        this.inorderTraversal(this.root);
    }

    // 中序遍历， 可以在按照升序或者降序的方式展示
    protected void inorderTraversal(Node<E> node) {
        if (node == null) {
            return;
        }
        this.inorderTraversal(node.left);
        System.out.println(node.element);
        this.inorderTraversal(node.right);
    }

    // 前序遍历
    public void preorderTraversal() {
        this.preorderTraversal(this.root);
    }

    // 前序遍历
    protected void preorderTraversal(Node<E> node) {
        if (node == null) {
            return;
        }
        System.out.println(node.element);
        this.preorderTraversal(node.left);
        this.preorderTraversal(node.right);
    }

    // 层序遍历，
    public void evelOrderTranversal() {
        if (this.root == null) {
            return;
        }
        Queue<Node<E>> queue = new LinkedList<Node<E>>();
        queue.offer(this.root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            System.out.println(node.element);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }



    // 判断一棵树算不算完全二叉树
    public boolean isComplete() {
        if (root == null) return false;

        // 标记后面是否应该全为叶子节点
        boolean isLeafLater = false;

        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(this.root);

        while (!queue.isEmpty()) {

            Node<E> node = queue.poll();
            if (isLeafLater && !node.isLeaf()) return false;

            // 先把该添加的都添加进去， 然后再分类，
            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) {
                return false;
            }

            if (node.right != null) {
                queue.offer(node.right);
            } else {
                isLeafLater = true;
            }
        }

        return true;

    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    public void clear() {
        this.size = 0;
    }

    // 打印数状结构
    public String toString() {
        StringBuilder sb = new StringBuilder();
        this.toString(this.root, sb, "");
        return sb.toString();
    }

    private void toString(Node<E> node, StringBuilder sb, String prefix) {
        if (node == null) {
            return;
        }
        this.toString(node.right, sb, prefix + "[R]");
        sb.append(prefix).append(node.element).append("\n");
        this.toString(node.left, sb, prefix + "[L]"); // 告诉他你是左还是右边

    }

    protected static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        public boolean isLeaf() {
            return this.left == null && this.right == null;
        }

        public boolean isLeftChild(){
            return parent != null && this == parent.left;
        }

        public boolean isRighrChild(){
            return parent != null && this == parent.right;
        }

        public boolean hasTwoChildren() {
            return this.left != null && this.right != null;
        }
    }
}
